#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <string.h>

// 说明：将来任何使用本通用队列的程序，需要重新定义以下宏：
// QUEUE_DATATYPE
// 否则，默认存储int

#ifndef QUEUE_DATATYPE
#define QUEUE_DATATYPE int
#endif

typedef QUEUE_DATATYPE queue_datatype;

// 链表的节点
typedef struct node
{
    queue_datatype data;
    struct node *next;
}node, *list;

// 队列的管理结构体
typedef struct
{
                   //  front                 rear
                   //   ↓                     ↓ 
    list front;    //   囗 --> 囗 --> 囗  --> 囗  --> NULL
    list rear;
    int size; // 队列元素总数
}queue;


bool is_empty(queue *q)
{
    return q->size == 0;
}

queue *init_queue(void)
{
    queue *q = calloc(1, sizeof(queue));
    if(q != NULL)
    {
        q->front = NULL;
        q->rear  = NULL;
        q->size  = 0;
    }
    return q;
}

list new_node(queue_datatype data)
{
    list newnode = calloc(1, sizeof(node));
    if(newnode != NULL)
    {
        newnode->data = data;
        newnode->next = NULL;
    }
    return newnode;   
}

// newnode入队，排到队尾
bool en_queue(queue *q, list newnode)
{
    if(is_empty(q))
    {
        q->front = q->rear = newnode;
    }
    else
    {
        q->rear->next = newnode;
        q->rear = newnode;
    }

    q->size++;
    return true;
}

bool out_queue(queue *q, list *k)
{
    if(is_empty(q))
        return false;

    *k = q->front;
    q->front = q->front->next;
    (*k)->next = NULL;
    q->size--;

    if(q->size == 0)
        q->rear = NULL;

    return true;
}

bool front_queue(queue *q, list *k) // 取队头元素
{
    if(is_empty(q))
        return false;

    *k = q->front;
    return true;
}



void destroy_init(queue *q) // 将队列恢复初始状态
{

}
void destroy(queue *q)
{}

// 提供一种遍历队列的接口，如何访问遍历到的节点，就交给用户的钩子函数
void list_for_each(queue *q, void (*handler)(queue_datatype))
{
    if(is_empty(q))
        return;

    for(list p=q->front; p!=NULL; p=p->next)
    {
        handler(p->data);
    }
}

#endif